翻訳と辞書 Words near each other ・ Random number table ・ Random optimization ・ Random oracle ・ Random orbital sander ・ Random Passage ・ Random password generator ・ Random permutation ・ Random permutation statistics ・ Random phase approximation ・ Random phase multiple access ・ Random plot generator ・ Random positioning machine ・ Random projection ・ Random Quest ・ Random Recipe ・ Random regular graph ・ Random Roads Collection ・ Random search ・ Random seed ・ Random self-reducibility ・ Random sequence ・ Random Shoes ・ Random Spirit Lover ・ Random stimulus ・ Random structure function ・ Random subspace method ・ Random test generator ・ Random testing ・ Random Thoughts ・ Random Thoughts (Don Pullen album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Random regular graph ： ウィキペディア英語版 Random regular graph A random ''r''-regular graph is a graph selected from $\backslash mathcal\_$, which denotes the probability space of all ''r''-regular graphs on ''n'' vertices, where 3 ≤ ''r'' < ''n'' and ''nr'' is even.〔Béla Bollobás, ''Random Graphs'', 2nd edition, Cambridge University Press (2001), section 2.4: Random Regular Graphs〕 It is therefore a particular kind of random graph, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular. ==Properties of random regular graphs== As with more general random graphs, it is possible to prove that certain properties of random ''r''-regular graphs hold almost surely. In particular, for $r\; \backslash ge\; 3$, a random ''r''-regular graph of large size is almost surely ''r''-connected.〔Bollobás, section 7.6: Random Regular Graphs〕 In other words, although ''r''-regular graphs with connectivity less than ''r'' exist, the probability of selecting such a graph tends to 0 as ''n'' increases. If $\backslash epsilon$ > 0 is a positive constant, and ''d'' is the least integer satisfying $(r-1)^\; \backslash ge\; (2\; +\; \backslash epsilon)rn\; \backslash ln\; n$ then, almost surely, a random ''r''-regular graph has diameter at most ''d''. There is also a (more complex) lower bound on the diameter of ''r''-regular graphs, so that almost all ''r''-regular graphs (of the same size) have almost the same diameter.〔Bollobás, section 10.3: The Diameter of Random Regular Graphs〕 The distribution of the number of short cycles is also known: for fixed ''m'' ≥ 3, let ''Y''3,''Y''4,…,''Y''''m'' be the number of cycles of lengths up to ''m''. Then the ''Y''''i'' are asymptotically independent Poisson random variables with means〔Bollobás, section 2.4: Random Regular Graphs (Corollary 2.19)〕 $\backslash lambda\_i=\backslash frac$ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Random regular graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.